// 动态规划（Dynamic Programming，DP）是一种将复杂问题分解成更小的子问题来解决的优
// 化技术。
// 用动态规划解决问题时，要遵循三个重要步骤：
// (1) 定义子问题；
// (2) 实现要反复执行而解决子问题的部分（这一步要参考前一节讨论的递归的步骤）；
// (3) 识别并求解出边界条件。
function MinCoinChange(coins) {
  var coins = coins; //{1} 
  var cache = {}; //{2} 
  this.makeChange = function (amount) {
    var me = this;
    if (!amount) { //{3} 
      return [];
    }
    if (cache[amount]) { //{4} 
      return cache[amount];
    }
    var min = [], newMin, newAmount;
    for (var i = 0; i < coins.length; i++) { //{5} 
      var coin = coins[i];
      newAmount = amount - coin; //{6} 
      if (newAmount >= 0) {
        newMin = me.makeChange(newAmount); //{7} 
        console.log(newMin)
      }
      if (
        newAmount >= 0 && //{8} 
        (newMin.length < min.length - 1 || !min.length)//{9} 
        && (newMin.length || !newAmount) //{10} 
      ) {
        min = [coin].concat(newMin); //{11} 
        console.log('new Min ' + min + ' for ' + amount);
      }
    }
    return (cache[amount] = min); //{12} 
  };
}
var minCoinChange = new MinCoinChange([1, 5, 10, 25]); 
console.log(minCoinChange.makeChange(5));
